\documentclass[a4paper,12pt]{article}

\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{cmap} % можно копировать текст
%\defaulthyphenchar=127
\usepackage[T2A]{fontenc}
\usepackage{latexsym}
\usepackage{amsfonts}
\usepackage{amssymb, amsmath}
\usepackage{amsthm} % for {proof}
\usepackage{indentfirst}
\usepackage{geometry}
\usepackage{enumerate}
\geometry{a4paper}
% Для работы с цветом
\usepackage[usenames]{color}
% Данная команда обеспечивает автоматическое генерирование гиперссылок в статье на формулы и/или цитированную литературу в том случае, если в статье используются LaTeXовские механизмы перекрестных ссылок
\usepackage{hyperref}
% Для графики
\usepackage{tikz}
\usetikzlibrary{automata,shapes,arrows,positioning,calc}
% Для описания алгоритмов
\usepackage{clrscode}
\usepackage{sectsty}
\usepackage{verbatim}

\newcommand{\nspace}{\hspace{0pt}}
\newcommand{\nbdash}{\nobreakdash-\nspace}
\renewcommand{\qed}{\hfill \vrule width1.5ex height1.5ex depth0pt}
\newcommand{\eqdef}{\ensuremath{\stackrel{\text{\upshape\tiny def}}{=}}}

\DeclareMathOperator{\AP}{AP}
\DeclareMathOperator{\Id}{Id}

\newtheorem{Thm}{Теорема}[section]
\newtheorem{Lmm}{Лемма}
\newtheorem{Cor}{Следствие}
\newtheorem*{Remark}{Замечание}
\newtheorem*{Algo}{Алгоритм}

\theoremstyle{definition}
\newtheorem*{Def}{Определение}
\newtheorem{NumAlgo}{Алгоритм}[section]
\newtheorem{Exmpl}{Пример}

\newcommand{\N}{\ensuremath{\mathbb N}}
\newcommand{\NO}{\ensuremath{\mathbb N_0}}
\newcommand{\Tau}{\ensuremath{\mathrm T}}
\newcommand{\pset}{\mathcal P}

\frenchspacing

\title{Нахождение множества длин слов формального языка}
\author{}

\begin{document}
\maketitle

\begin{abstract}
	Рассматривается задача нахождения длин слов формального языка. Для этого максимально упрощается язык, но так, чтобы искомое множество длин не изменилось. Упрощённый язык получается из данного формального языка посредством отождествления всех букв алфавита (полученный язык называется <<отождествлением>> исходного языка). Рассмотрены способы описания отождествлённого языка, прежде всего, теоретико\nbdash{}языковой способ: указание грамматики и класса иерархии Хомского, которому будет принадлежать отождествлённый язык. Отмечено, что изучение сложности отождествлённого языка можно проводить арифметическими методами. Используя нотацию отождествлённых языков, приводятся алгоритмы, позволяющие явно вычислить длины слов праволинейных и контекстно\nbdash{}свободных языков, заданных своей грамматикой. Доказывается, что вычисление множества длин слов контекстно\nbdash{}зависимых языков~--- неразрешимая проблема. Представлена удобная характеризация класса языков, отождествление которых праволинейно, в терминах порождающей язык грамматики.
\end{abstract}


\tableofcontents


\section{Введение}

Алфавитом называется любое конечное множество, словом над алфавитом $\Sigma$ называется элемент свободного моноида $\Sigma^*$, под формальным языком $L$ (или просто: языком $L$) над алфавитом $\Sigma$ понимается произвольное множество слов над $\Sigma$, этот факт записывается так: $L \in \pset(\Sigma^*)$.

Везде далее, где упоминается «язык над однобуквенным алфавитом»,  подразумевается некоторый фиксированный однобуквенный алфавит $\Tau$. Например, $\Tau = \{ 1 \}$. 
% Для любого алфавита $\Sigma$ отображение $\Id_\Sigma$ индуцирует гомоморфизм свободных моноидов и более того, само является гомоморфизмом $\Id \colon \Sigma^* \to \Tau^*$ (образ морфизма $\Id_\Sigma$ под действием функтора свободного моноида), который в каждом слове над алфавитом $\Sigma$ заменяет каждую букву на единственный символ алфавита $\Tau$. 

Единственное отображение из любого алфавита $\Sigma$ в $\Tau$ обозначается $\Id_\Sigma$. Действие $\Id_\Sigma \colon \Sigma \to \Tau$ можно продолжить до действия на $\Sigma^*$. Отображение $\Id_\Sigma$ в каждом слове над алфавитом $\Sigma$ заменяет каждую букву на единственный символ алфавита $\Tau$. Пусть $w=c_1 c_2 \dots c_n$~--- $n$\nbdash{}буквенное слово языка $L$ над алфавитом $\Sigma$, тогда действие гомоморфизма $\Id_\Sigma$ можно описать следующим образом:
$$
     \Id_\Sigma \colon L \to \Tau^*, \quad  \Id_\Sigma(w) = \Id_\Sigma(c_1c_2\ldots c_n) = \underbrace{11\ldots 1}_n = 1^{n}
$$
В дальнейшем вместо $\Id_\Sigma$ будем писать просто $\Id$, если алфавит $\Sigma$ ясен из контекста или не важен. Через $\Id(L)$ обозначим множество слов из $\Tau^*$, которое может быть получено действием $\Id$ на слова языка $L$.
$$
     \Id \colon \pset(\Sigma^*) \to \pset(\Tau^*), \quad  \Id(L) = \{w \mid \exists v \in L, w = \Id(v)\}
$$

\begin{Def}
    Формальный язык $\Id(L) \in \pset(\Tau^*)$ будем называть \emph{отождествлением языка $L$} или \emph{отождествлённым языком}.
\end{Def}

Рассмотрим примеры отождествлённых языков.

\begin{Exmpl}
	Отождествлённый язык пустого языка пуст.
\end{Exmpl}

\begin{Exmpl}
	Пусть $\NO = \N \cup \{ 0 \}$. Отождествлённый язык языка $\Sigma^*$ совпадает с языком $\{1^n \mid n \in \NO\} $.
\end{Exmpl}

\begin{Exmpl}
	Язык $\{a^n b^n \mid n \in \NO\}$ под действием отображения $\Id$ перейдёт в $\{1^n 1^n \mid n \in \NO\} = \{1^{2n} \mid n \in \NO\}$.
\end{Exmpl}

В части~\ref{MainCriterionChap} обсуждается сложность языков $\Id(L)$ с точки зрения иерархии Хомского, для чего используется простая, но важная для дальнейших построений арифметическая характеризация таких языков (теорема~\ref{CriterionIdIsLG}). В части~\ref{GrammarsForIdsChap} приведены алгоритмы построения грамматик для отождествлений разных классов языков. В части~\ref{LengthsPLChap} приводится алгоритм нахождения множества длин слов праволинейного языка с использованием результатов частей~\ref{MainCriterionChap} и~\ref{GrammarsForIdsChap}. В части \ref{LengthsCFChap} приводится алгоритм нахождения множества длин слов контекстно\nbdash{}свободного языка с использованием результатов частей~\ref{MainCriterionChap} и~\ref{LengthsPLChap}. Проблема нахождения множества длин слов контекстно\nbdash{}зависимого языка неразрешима, что доказывается в части~\ref{LengthsCSChap}. В части~\ref{ApplicationChap} описаны некоторые связанные задачи.

Задача нахождения длин слов уже рассматривалась в книге \cite[глава 3]{Lando}. Там вводится производящая функция языка как формальный степенной ряд $l(s) = 1 + l_1 s + l_2 s^2 + \ldots$, где $l_k$ --- это количество слов длины $k$. В работе Ландо~С.~К. доказывается, что для грамматик с однозначным выводом можно построить производящую функцию языка $l(s)$, однако не приводится алгоритма, позволяющего сделать это. Более того, задача проверки на однозначность является неразрешимой. В той же работе доказано, что для некоторого класса контекстно-свободных языков можно построить производящую функцию языка по производящей функции $n(s)$ подъязыка неразложимых в нём слов и наоборот, но автоматическая проверка принадлежности грамматики данному классу и нахождение $n(s)$ являются нетривиальными задачами. Нам же удалось построить алгоритм, вычисляющий множество длин произвольной контекстно-свободной грамматики и выдающий результат в виде конечного набора арифметических последовательностей, а не производящей функции.

\section{Сложность отождествлённого языка}\label{MainCriterionChap}

В любом языке над однобуквенным алфавитом каждое слово однозначно идентифицируется своей длиной. Если такой язык является отождествлением некоторого другого языка, множества длин их слов, очевидно, совпадают. Введём обозначение для множества длин всех слов произвольного языка $L$:
$$
	M(L) = \{m \in \NO \mid \exists w \in L, |w| = m\}.
$$
Далее будем работать с языками, множество длин слов которых представляет собой объединение элементов арифметических прогрессий. Обозначим
$$
    \AP(a, d) = \{a+n d \mid n \in \NO \}.
$$

Следующая теорема даёт критерий принадлежности отождествления языка самому простому с точки зрения иерархии Хомского классу языков (праволинейным языкам) в терминах длин слов исходного языка.

\begin{Thm}\label{CriterionIdIsLG}
	Пусть  $L$~--- произвольный язык.  Язык $\Id(L)$ является праволинейным тогда и только тогда, когда множество $M(L)$ представимо в виде конечного объединения арифметических прогрессий.
\end{Thm}
\begin{proof}
	($\Rightarrow$)
	Предположим, что после отождествления язык $L$ стал праволинейным. Согласно лемме о накачке для регулярных языков, найдётся такое натуральное число $n$, что $\forall w \in L, |w| \geqslant n$ можно записать $w = xyz$, причём выполняются следующие условия:
	 \begin{enumerate}
	 	\renewcommand{\labelenumi}{\theenumi)}
	 	\item $y \neq \varepsilon$;
	 	\item $|xy| \leqslant n$;
	 	\item $\forall k \geqslant 0 \; x y^k z \in L$.
	 \end{enumerate} 
	 Множество $M(L)$ является объединением некоторого семейства арифметических прогрессий с основанием $|xz|$ и шагом $|y|$. 
	 У каждой прогрессии из $M(L)$ первый член и шаг не больше числа $n$. Существует лишь конечное число прогрессий натуральных чисел с таким ограничением, потому рассматриваемое семейство конечно.
	
	($\Leftarrow$)
	Пусть 
	$$
		M(L) = \bigcup_{i=1}^{n} \AP(a_i, d_i),
	$$
	тогда отождествлённый язык будет порождаться праволинейной грамматикой cо следующими продукциями:
	$\forall i = 1 \ldots n$
	\begin{equation*}
		\begin{array}{l}
			S \to 1^{a_i} D_i; \\
			D_i \to \varepsilon \mid 1^{d_i} D_i.
		\end{array}
	\end{equation*}
\end{proof}

Далее рассмотрим возможность попадания отождествления языка в класс праволинейных языков, исходя из теоретико-языковых свойств формальных языков. Для этого сначала приводятся факты, связанные с множествами, полученными из бесконечного семейства арифметических прогрессий. Пусть $A$ --- семейство арифметических прогрессий. Через $M(A)$ обозначим множество чисел, содержащихся в этих прогрессиях: $M(A) = \bigcup\limits_{p \in A} {p}$.

\begin{Lmm}[свойство компактности семейств арифметических прогрессий с общей разностью]\label{AkIsFiniteSet}
	Рассмотрим бесконечное множество $A^{(k)}$ арифметических прогрессий с фиксированной разностью $k \in \N.$ Существует конечное множество арифметических прогрессий $B^{(k)}$ с фиксированной разностью $k$ и выполняется равенство: $M(A^{(k)}) = M(B^{(k)})$.
\end{Lmm}
\begin{proof} 
	Положим 
	$$
		A^{(k, r)} = \{\AP(a, k) \in A^{(k)} \mid a \equiv r \pmod{k} \}
	$$
	для целого $r = \overline{0, k-1}$, тогда
	\begin{equation}\label{AkIsAkr}
		M(A^{(k)}) =  \bigcup_{r=0}^{k-1} M(A^{(k, r)}).
	\end{equation} 
	Зафиксируем $r$. Выберем среди первых членов последовательностей из  $A^{(k, r)}$ минимальное (оно существует, так как основания~--- неотрицательные целые числа) и обозначим его через $a^{(r)}_{min}$. Выполняется равенство:
	\begin{equation}\label{AkrIsOneAP}
		M(A^{(k, r)}) = \AP(a^{(r)}_{min}, k).
	\end{equation}
	Подставим равенство~\eqref{AkrIsOneAP} в~\eqref{AkIsAkr}:
	\begin{equation*}
		M(A^{(k)}) = \bigcup_{r=0}^{k-1} M(A^{(k, r)}) = \bigcup_{r=0}^{k-1} \AP(a^{(r)}_{min}, k).
	\end{equation*}
	Получим, что множество $A^{(k)}$ представимо в виде конечного объединения прогрессий, что и требовалось доказать.
\end{proof} 

\begin{Lmm}[свойство компактности семейств арифметических прогрессий с ограниченной разностью]\label{AIsFiniteSet}
	Зафиксируем $n \in \N$. Рассмотрим бесконечное множество арифметических прогрессий $A = \{\AP(a_1, d_1), \AP(a_2, d_2), \ldots \}$, таких что $d_i \leqslant n$. Существует конечное множество арифметических прогрессий $B$, такое что выполняется равенство: $M(A) = M(B).$
\end{Lmm}
\begin{proof}
	Множество $A$ представимо в виде конечного объединения: 
	\begin{equation}\label{AIsAi}
		A = \bigcup_{i=1}^n A^{(i)},
	\end{equation}	
	где $A^{(i)} = \{\AP(a, d) \in A \mid d = i\}$. В силу леммы~\ref{AkIsFiniteSet} для любого такого множества $A^{(i)}$ существует конечное множество $B^{(i)}$, такое что
	\begin{equation}\label{AiIsFinite}
		M(A^{(i)}) = M(B^{(i)}).
	\end{equation}
	Подставим равенство~\eqref{AiIsFinite} в~\eqref{AIsAi}:
	\begin{equation}
		M(A) = \bigcup_{i=1}^n M(A^{(i)}) = \bigcup_{i=1}^n M(B^{(i)}).
	\end{equation}
	Каждое из множеств $B^{(i)}$ конечно и, таким образом, $M(A)$ представлено в виде конечного объединения арифметический прогрессий.
\end{proof} 

\begin{Thm}\label{PumpingLangsAreSimple}
	Если для языка $L$ выполняется условие леммы о накачке для контекстно\nbdash{}свободных языков, то язык $\Id(L)$ праволинейный.
\end{Thm}
\begin{proof}
	Предположим, для языка $L$ выполняется лемма о накачке для контекстно\nbdash{}свободных языков. Согласно лемме, найдётся такое натуральное число $N$, что $\forall z \in L, |z| \geqslant N$ можно записать $w = uvwxy$, причём выполняются следующие условия:
	 \begin{enumerate}
	 	\item $|vx|  \neq \varepsilon$.
	 	\item $|vwx| \leqslant N$.
	 	\item $\forall k \geqslant 0 \; u v^k w x^k y \in L$.
	 \end{enumerate} 
	 Множество $M(L)$ является объединением конечного множества 
	 $$
		M = \{|w| \mid  \exists w \in L, |w| < N \}
	$$
	 и некоторого семейства арифметических прогрессий с основанием $|uwy|$ и шагом $|vx|$. Шаг каждой прогрессии из $M(L)$ не превосходит $N$. По лемме~\ref{AIsFiniteSet} и в силу конечности $M$, $M(L)$ представимо в виде конечного объединения арифметических последовательностей. Следовательно, по теореме~\ref{CriterionIdIsLG}, язык $\Id(L)$ праволинейный.
\end{proof}

\begin{Cor}\label{IdCFisPL}
	Отождествление любого контекстно\nbdash{}свободного языка является праволинейным языком.
\end{Cor}

\begin{Cor}\label{IdCFIsNoCF}
	Над однобуквенным алфавитом не существует контекстно\nbdash{}свободного языка, не являющегося праволинейным.
\end{Cor}
\begin{proof}
	Пусть $L$~--- контекстно\nbdash{}свободный язык над однобуквенным алфавитом. Язык $L$ совпадает со своим отождествлением: $L = \Id(L).$ По следствию \ref{IdCFisPL} язык $\Id(L)$ является праволинейным.
\end{proof}

В книге \cite[стр. 41]{Pen} приведено доказательство следствия \ref{IdCFIsNoCF} не использующее нотацию отождествлений, но близкое по содержанию к доказательству теоремы \ref{PumpingLangsAreSimple}.

Для следующего в иерархии Хомского класса языков~--- контекстно\nbdash{}зависимых языков~--- отождествления некоторых языков этого класса являются праволинейными.

\begin{Exmpl}[\{ $a^nb^nc^n$ \}]
	Язык $\Id(\{a^nb^nc^n \mid n \in \N, \; n \geq 2\}) = \{1^{3n} \mid n \in \N, \; n \geq 2\}$, очевидно, праволинеен. Этот пример показывает, что обращение теоремы \ref{PumpingLangsAreSimple} неверно.
\end{Exmpl}

Не для всех контекстно\nbdash{}зависимых языков, однако, их отождествления праволинейны.
\begin{Exmpl}[$\{ 1^{2^n} \}$]
	Рассмотрим язык $L = \{1^{2^n} \mid n \in \N \; n \geq 2\}$, задаваемый грамматикой $G = (\{1\}, \{S, F, L, T, E\}, \mathcal P, S)$, $\mathcal P$:
	\begin{equation*}
		\begin{array}{l}
			S \to F11TL \\
			FT \to F\\
			L \to TL\\
			1T \to T11\\
			L \to E\\
			1E \to E1\\
			FE \to \epsilon
		\end{array}
	\end{equation*}
	Язык $L$ задан над однобуквенным алфавитом и его отождествление совпадает с ним самим: $L = \Id(L).$ Множество длин слов $M(L) = \{ 2^n \mid n \in \N, \; n \geq 2 \}$ нельзя представить как конечное объединение арифметических прогрессий, следовательно, по теореме~\ref{CriterionIdIsLG}, язык $L(G)$ не является праволинейным.
\end{Exmpl}

%Теорему~\ref{CriterionIdIsLG}, характеризующую языки, отождествление которых праволинейно, сложно применять на практике, так как множество длин слов языка чаще всего неизвестно или выделить в нём арифметические прогрессии не представляется возможным. Теорема~\ref{PumpingLangsAreSimple} даёт только достаточное условие. 


\section{Грамматика отождествлённого языка}\label{GrammarsForIdsChap}

В этой части формулируются и обосновываются алгоритмы, сопоставляющие грамматике языка грамматику его отождествления.

\begin{NumAlgo}[Построение грамматики отождествления контекстно\nbdash{}свободного языка]\label{CFG4Id}
\nspace\\
\textsc{Вход}: контекстно\nbdash{}свободная грамматика $G = (\Sigma, N, \mathcal P, S \in N)$.\\
\textsc{Выход}: контекстно\nbdash{}свободная грамматика $G' = (\Sigma', N', \mathcal P', S' \in N')$, такая что $L(G') = \Id(L(G))$.
\begin{enumerate}
	\item 
		\begin{codebox}
			$\Sigma' \gets \{1\}$ \\
			$N' \gets N$ \\
			$S' \gets S$ \\
			$\mathcal P' \gets \mathcal P$
		\end{codebox}
	\item % посмотреть как уменьшить здесь межстрочное расстояние
		В продукциях $\mathcal P'$ все терминалы, встречающиеся в правых частях продукций, заменить на терминал $1$.
\end{enumerate}
\end{NumAlgo}

\begin{Thm}[корректность алгоритма~\ref{CFG4Id}]
	Пусть $G = (\Sigma, N, \mathcal P, S \in N)$~--- контекстно\nbdash{}свободная грамматика, $G' = (\Sigma', N', \mathcal P',$ $S' \in N')$~--- грамматика, полученная из $G$ по алгоритму~\ref{CFG4Id}. Язык, порождаемый грамматикой $G'$, совпадает с отождествлением языка $L(G)$: $$L(G') = \Id(L(G)).$$
\end{Thm}
\begin{proof}
	% по примеру доказательства из книги Хопкрофта Введение в теорию\ldots, стр 206
	Докажем вложение $L(G') \supset \Id(L(G)).$ Покажем, что $\forall w \in L(G) \; 1^{|w|} \in L(G')$. Доказательство поведём по индукции по длине цепочки вывода $A' \to^* w, A \in N'$.
	
	\textbf{Базис.} Если вывод состоит из одного шага, то в грамматике $G$ есть продукция $A \to w$, стало быть в грамматике $G'$ должна быть продукция, полученная из данной заменой нетерминалов в правой части. Таким образом, продукция $A \to 1^{|w|}$ принадлежит $\mathcal P'$ и, соответственно, в $G'$ из $A$ выводимо слово $1^{|w|}$.
	
	\textbf{Индукция.} Пусть вывод состоит из $n+1$ шагов и пусть для любого вывода из $n$ и менее шагов утверждение выполняется. Запишем вывод в виде $S \to X_1X_2\ldots X_k \to^* w$. Тогда можно представить $w$ как $w=w_1w_2\ldots w_k$~\cite[п. 5.2.6] {HMU}, где:
	\begin{enumerate}
	\renewcommand{\theenumi}{\asbuk{enumi}}
		\item если $X_i$~--- терминал, то $w_i = X_i$;
		\item если $X_i$~--- переменная, то $X_i \to^* w_i$. Так как первый шаг вывода $S \to^* w$ не является частью вывода $X_i \to^* w_i$, то известно, что этот вывод состоит из $n$ или менее шагов. Таким образом, к нему применимо предположение индукции, и можно заключить, что $w_i$ принадлежит языку $X_i$.
	\end{enumerate}
	
	Теперь есть продукция $S \to X_1X_2\ldots X_k$, и известно, что $w_i$ или равно $X_i$, или принадлежит языку $X_i$. Получается, что слово 
	$$
		1^{|w_1|} 1^{|w_2|}\ldots 1^{|w_k|} = 1^{|w_1| + |w_2| + \ldots + |w_k|} = 1^{|w|}
	$$
	принадлежит языку, порождённому грамматикой $G'$ доказана.
    
    Доказательство прямого вложения $L(G') \subset \Id(L(G))$ очевидно.
\end{proof}
	
\begin{Remark}
Грамматика, построенная с помощью алгоритма~\ref{CFG4Id} в общем случае не является праволинейной, хотя по следствию теоремы~\ref{PumpingLangsAreSimple}, язык этой грамматики праволинеен. В части \ref{LengthsCFChap} приведён алгоритм нахождения множества длин слов языка в виде конечного объединения арифметических прогрессий. Зная набор прогрессий, входящих в объединение, можно построить праволинейную грамматику отождествления языка.
\end{Remark}

Идея алгоритма~\ref{CFG4Id} не может быть перенесена на класс контекстно\nbdash{}зависимых языков.

\begin{Exmpl}
Рассмотрим контекстно\nbdash{}зависимую грамматику $G = (\{S, D\},$ $\{a, b\},$ $\mathcal P,$ $S)$, $\mathcal P$:
 	\begin{equation*}
 	\begin{array}{ll}
 		(1)& S \to aaD \\
 		(2)& S \to bbbD \\
 		(3)& aaD \to aa \\
 		(4)& aaD \to aaaaD \\
 		(5)& bbbD \to bbb \\
 		(6)& bbbD \to bbbbbbD.
 	\end{array}
 	\end{equation*}
 	Она порождает слова длины кратной двум или трём:
    $$
        L(G) = \{ a^{2i} \cup b^{3j} \mid i, j \in \N \}.
    $$
	Заменим все нетерминалы грамматики на $1$, получим грамматику $G' = (\{S', D'\}, \{1\}, \mathcal P', S')$, $\mathcal P'$:
	\begin{equation*}
 	\begin{array}{ll}
 		(1')& S' \to 11D' \\
 		(2')& S' \to 111D' \\
 		(3')& 11D' \to 11 \\
 		(4')& 11D' \to 1111D' \\
 		(5')& 111D' \to 111 \\
 		(6')& 111D' \to 111111D'.
 	\end{array}
 	\end{equation*}
	В полученной грамматике возможен вывод слова длины 7:
	$$
		S' \stackrel{(2')}{\to} 11D' \stackrel{(4')}{\to} 1111D' \stackrel{(6')}{\to} 1111111D' \stackrel{(5')}{\to} 1111111.
	$$
	Но 7 не кратно двум или трём, легко убедиться, что в $L(G)$ нет слова длины 7, получаем что $L(G') \neq \Id(L(G))$.
	
	%Заметим также, что при выводе цепочки 1111111 использовалась последовательность продукций $(2'), (4'), (6'), (5')$, которая недопустима в исходной грамматике: $$ S \stackrel{(2)}{\to} aaD. $$
\end{Exmpl}


\begin{NumAlgo}[Построение грамматики отождествления контекстно\nbdash{}зависимого языка]\label{CNfG4Id}
\nspace\\
\textsc{Вход}: контекстно\nbdash{}зависимая грамматика $G = (\Sigma, N, \mathcal P, S \in N)$.\\
\textsc{Выход}: контекстно\nbdash{}зависимая грамматика $G' = (\Sigma', N', \mathcal P', S' \in N')$, такая что $L(G') = \Id(L(G))$.
\begin{codebox}
\li\label{CNfG4Id_step1} 
	$\Sigma' \gets \{1\}$ \\
	$N' \gets N \cup \Sigma$ \Comment Терминалы из $G$ стали нетерминалами в $G'$.\\
	$S' \gets S$ \\
	$\mathcal P' \gets \mathcal P$
\li\label{CNfG4Id_step2}
	$\forall a \in \Sigma$ добавить в $\mathcal P'$ продукцию $a \to 1$.
\end{codebox}
\end{NumAlgo}

\begin{Thm}[корректность алгоритма~\ref{CNfG4Id}]
	Пусть $G = (\Sigma, N, \mathcal P,$ $S \in N)$~--- контекстно\nbdash{}зависимая грамматика, $G' = (\Sigma', N', \mathcal P',$ $S' \in N')$~--- грамматика, полученная из $G$ по алгоритму~\ref{CNfG4Id}. Язык, порождаемый грамматикой $G'$, совпадает с отождествлением языка $L(G)$: $$L(G') = \Id(L(G)).$$	
\end{Thm}
\begin{proof}
	Докажем вложение $\Id(L(G)) \subset L(G')$, для этого выберем произвольное слово $w \in L(G)$ и покажем, что $1^{|w|} \in L(G')$. Каждая из продукций, использовавшихся при выводе $S \to^* w$, была добавлена в $\mathcal P'$ на шаге~\ref{CNfG4Id_step1}, а значит нетерминальная цепочка $w$ выводима в $G'$. Так как $w$~--- слово в $L(G)$, то $w \in \Sigma^*$. Для каждого символа из $w$ применим продукции добавленные на шаге~\ref{CNfG4Id_step2} и получим слово той же длины, но состоящее из единиц.
	
	Докажем обратное вложение $L(G') \subset \Id(L(G))$. Выберем произвольное слово $1^{n} \in L(G'), n \in \N \cup \{0\}$ и покажем, что $1^{n} \in \Id(L(G))$ или, что то же самое, $\exists w \in L(G)$ такое что $|w| = n$. Для этого установим следующий порядок вывода в $G'$: сначала будем использовать  только продукции, добавленные в грамматику на шаге~\ref{CNfG4Id_step1} алгоритма~\ref{CNfG4Id}, а когда терминальная цепочка будет  принадлежать $\Sigma^+$, то воспользуемся продукциями, добавленными на шаге~\ref{CNfG4Id_step2} и переведём каждую букву цепочки в 1. Рассмотрим вывод в грамматике $G':$
	$$S' \to^* w \to^* 1^{|w|},$$
    где $w$ принадлежит $\Sigma^+$. Каждая из продукций, использовавшихся при выводе $w$, принадлежит и продукциям $G$ (иначе её не было бы в $\mathcal P'$), следовательно, в $G$ выводима терминальная цепочка $w$ и $1^{|w|} \in \Id(L(G))$.
\end{proof}

Нахождение праволинейной грамматики для отождествления контекстно-зависимого языка (в случае, если оно праволинейно) остаётся открытой проблемой.


\section{Множество длин слов праволинейного языка}\label{LengthsPLChap}

Отождествление $\Id(L)$ языка $L$ тесно связано с множеством длин слов $L$ (теорема~\ref{CriterionIdIsLG}). В части~\ref{MainCriterionChap} отождествления разных классов языков изучались с помощью рассмотрения множеств длин слов исходных языков. В текущей части, наоборот, задача нахождения множества длин слов языка будет решена в простом частном случае праволинейных языков с использованием отождествления языка. Для этого будет применён полученный в части~\ref{GrammarsForIdsChap} алгоритм построения грамматики отождествления языка. Кроме того, для изучения длин слов понадобится несколько фактов из теории графов.    

\begin{Thm}[{Основная теорема о деревьях \cite[т. 7.13]{Erus}}] Для графа $G$ следующие утверждения равносильны:
    \begin{enumerate}
        \item Граф $G$~--- дерево.
        \item $G$ связный и количество рёбер на единицу меньше количества вершин.
        \item Любые две вершины $G$ можно соединить простым путём, притом единственным.
        \item $G$ ациклический, и добавление к нему нового ребра приводит к образованию единственного простого цикла.
    \end{enumerate}
\end{Thm}

\begin{Def}
    Пусть $G$~--- ориентированный граф. \emph{Полустепень исхода} вершины графа $G$~--- это число исходящих из неё рёбер, а \emph{полустепень захода}~--- число входящих в данную вершину рёбер.
\end{Def}

\begin{Lmm}\label{GraphHasntCycles}
 	Пусть $G$~--- связный ориентированный граф, полустепень исхода каждой вершины которого равна нулю или единице и есть вершина, полустепень исхода которой равна нулю, тогда $G$ не имеет циклов.
\end{Lmm}
\begin{proof}
	Пусть $V$~--- количество вершин в графе $G$, $E$~--- число дуг. С одной стороны, выполняется неравенство $E \geq V-1$, так как граф связный и к каждой вершине примыкает хотя бы одна дуга. С другой стороны, полустепень исхода каждой вершины не превосходит $1$, но есть вершина, полустепень исхода которой равна нулю, следовательно сумма полустепеней исхода всех вершин не превосходит $V-1$. Получаем оценку сверху для $E$: $E \leqslant V-1$. Таким образом, $E = V-1$, следовательно, по основной теореме о деревьях, граф $G$ является деревом и не имеет циклов.
\end{proof}

\begin{Lmm}\label{GraphHasOneCycle}
 	Пусть $G$~--- связный ориентированный граф, полустепень исхода каждой вершины которого равна 1, тогда в $G$ существует единственный простой цикл (петлю считаем простым циклом длины 1).
\end{Lmm}
\begin{proof}
	Существование. Выберем произвольную вершину $v_1$ графа $G$, её полустепень исхода равна единице, а, значит, есть дуга $(v_1, v_2)$ в вершину $v_2$, полустепень исхода вершины $v_2$ тоже равна единице, значит, есть дуга из неё в некоторую вершину $v_3$\ldots{} Повторяя рассуждения, можно построить бесконечный путь $\mu = v_1, v_2, v_3, \ldots$ на графе $G$, но вершин в $G$ конечное число, следовательно, в $\mu$ есть повторяющиеся вершины, а на графе $G$~--- цикл.
	
	Единственность. Удалим из графа $G$ дугу $(v, w)$, не являющуюся мостом (такая дуга существует, поскольку на графе есть цикл). После удаления дуги степень исхода одной вершины уменьшилась на единицу, и, по лемме~\ref{GraphHasntCycles}, полученный граф является деревом (связным графом без циклов). Добавим к нему дугу $(v, w)$ и получим исходный граф $G$. По основной теореме о деревьях, при добавлении одной дуги к графу\nbdash{}дереву появится ровно один цикл. Следовательно, в исходном графе $G$ был ровно один цикл.
\end{proof}

\begin{Thm}\label{GraphHasLeq1Cycle}
 	Пусть $G$~--- связный ориентированный граф, полустепень исхода каждой вершины которого равна нулю или единице, тогда $G$ имеет не более одного простого цикла.
\end{Thm}
\begin{proof}
	Если полустепень всех вершин равна единице, попадаем в условие леммы~\ref{GraphHasOneCycle} и граф имеет ровно один цикл, в противном случае есть хотя бы одна вершина с полустепенью исхода равной нулю и, по лемме~\ref{GraphHasntCycles}, граф не имеет циклов.
\end{proof}
 
\begin{NumAlgo}[Нахождение длин слов языка, заданного праволинейной грамматикой]\label{FindLenthsPLAlg}
\nspace\\
\textsc{Вход}: Праволинейная грамматика $G$.\\
\textsc{Выход}: Множество длин слов $M$ языка $G$. 
\Comment $M$ будем искать в виде конечного объединения арифметических прогрессий.
\begin{enumerate}
	\item По заданной грамматике $G$ получим праволинейную грамматику $G'$ языка $\Id(L(G))$, используя алгоритм~\ref{CFG4Id}.
	\item По грамматике $G'$ построим автомат $A$.
	\item Проведём процедуру детерминизации автомата $A$, получим автомат $A' = (Q', \sum', \delta', q_0', F')$. Автомат $A'$ в графовом представлении будет иметь один из следующих видов:

	\begin{enumerate}
	%\renewcommand{\theenumi}{\asbuk{enumi}}
		\item\label{AutomataForFiniteLang} \hspace{0pt}\\
		\begin{tikzpicture}[>=stealth', /tikz/initial text=, node distance=2cm,auto,every state/.style={very thick}]
			\node[state,initial] (q'_0) {$q'_0$};
			\node[state] (q'_1) [right of=q'_0] {$q'_1$};
			\node[state,style={draw=white!50}] (q'_{dots1}) [right of=q'_1] {$\ldots$};
			\node[state] (q'_n) [right of=q'_{dots1}] {$q'_n$};		
			\path[->] 
				(q'_0) edge node {1}(q'_1)
				(q'_1) edge node {1}(q'_{dots1})
				(q'_{dots1}) edge node {1}(q'_n);
		\end{tikzpicture}

		\item\label{AutomataForInfiniteLang} \hspace{0pt}\\
		\begin{tikzpicture}[>=stealth', /tikz/initial text=, minimum size=4mm,inner sep=0pt, node distance=2cm,auto,every state/.style={very thick}]
			\node[state,initial] (q'_0) {$q'_0$};
			\node[state] (q'_1) [right of=q'_0] {$q'_1$};
			\node[state,style={draw=white!50}] (q'_{dots1}) [right of=q'_1] {$\ldots$};
			\node[state] (q'_{m-1}) [right of=q'_{dots1}] {$\scriptstyle q'_{m-1}$};
			\node[state] (q'_m) [right of=q'_{m-1}] {$q'_m$};
					\node[state] (q'_{m+1}) [right of=q'_m] {$\scriptstyle q'_{m+1}$};
			\node[state,style={draw=white!50}] (q'_{dots2}) [below of=q'_{m+1}] {$\ldots$};
			\node[state] (q'_n) [left of=q'_{dots2}] {$q'_{m+k}$};
			
			\path[->] 
				(q'_0) edge node {1}(q'_1)
				(q'_1) edge node {1}(q'_{dots1})
				(q'_{dots1}) edge node {1}(q'_{m-1})
				(q'_{m-1}) edge node {1}(q'_m)
				(q'_m) edge node {1}(q'_{m+1})
				(q'_{m+1}) edge node {1}(q'_{dots2})
				(q'_{dots2}) edge node {1}(q'_n)
				(q'_n) edge node {1}(q'_m)
				;
		\end{tikzpicture}
	\end{enumerate}

	\begin{Remark}
		Без потери общности можно считать, что после детерминизации граф остаётся связным. Если это не так, рассматривать будем только компоненту связности содержащую начальное состояние. 
	\end{Remark}

	\begin{Remark}
		Наиболее важное свойство полученного графа: степень исхода каждой вершины равна нулю или единице, так как автомат детерминированный и в алфавите ровно одна буква, а потому, по теореме~\ref{GraphHasLeq1Cycle}, на графе не более одного простого цикла.
	\end{Remark}

	% \textcolor{red}{(можно доказать, что длина цикла равна НОК разностей АП-ий ???)}.

	\item Кратчайшее расстояние от $v_1$ до $v_2$ обозначим через $d(v_1, v_2)$ . Без нарушения общности можно считать, что все вершины достижимы из начальной, поскольку граф связный (смотри первое замечание), поэтому значение $d(q_0', v)$ определено для любой вершины $v$.

	Рассмотрим значение $M$ для каждого из графов:
	\begin{enumerate}
		\item
		\begin{equation}\label{lengsOfWords}
			M \gets \bigcup\limits_{f \in F'} {d(q_0', f)}.
		\end{equation}
		\item Пусть $C$~--- множество вершин, входящих в цикл, тогда
		\begin{equation}\label{lengsOfWordsCycle}
			M \gets \bigcup\limits_{f \in F' \setminus C} {d(q_0', f)} \cup  \bigcup\limits_{f \in F' \cap C} {\AP( d(q_0', f), |C|)}.
		\end{equation}
	\end{enumerate}
\end{enumerate}
\end{NumAlgo}
	Дадим некоторые пояснения формулам выше. Для каждого допускающего состояния не вошедшего в $C$ есть только одно слово, которое может прочитать автомат, остановившись в этом состоянии. Длина этого слова~--- $d(q_0', f)$. Часть $\bigcup\limits_{f \in F' \setminus C} {d(q_0', f)}$ означает, что в $M$ добавляется конечное число слов, которые не вошли ни в одну арифметическую прогрессию. Допускающим состояниям находящимся в цикле можно однозначно сопоставить арифметические последовательности. Первый член такой прогрессии равен $d(q_0', f)$, $f \in  F' \cap C$, а шаг равен $|C|$. Таким образом, прогрессия, соответствующая состоянию $f \in C$, есть $\AP( d(q_0', f), |C|)$. В формуле выше берётся объединение всех таких прогрессий.


\subsection*{Примеры}

Рассмотрим примеры нахождения множества длин слов для языков, заданных праволинейной грамматикой.

\begin{Exmpl}
	Пусть $L$~--- конечный регулярный язык, заданный грамматикой $G = (\{a, b, c\}, \{S\}, \mathcal P, S)$, $\mathcal P$:
	\begin{equation*}
	\begin{array}{l}
		S \to a \mid ba \mid bb \mid cb \mid cccc.
	\end{array}
	\end{equation*}

	Подадим грамматику $G$ на вход алгоритму~\ref{FindLenthsPLAlg}.
	\begin{enumerate}
		\item
		На первом шаге алгоритма получим новую грамматику $G' = (\{1\}, \{S\}, \mathcal P',$ $S)$ для отождествлённого языка $\Id(L(G))$, $\mathcal P'$:
		\begin{equation*}
			\begin{array}{l}
				S \to 1 \mid 11 \mid 1111.
			\end{array}
		\end{equation*}

		\item 
		Автомат $A$, распознающий язык $L(G')$ имеет вид $$A = (\{q_0, q_1, q_2, q_3, q_4\}, \{1\}, \delta, q_0, \{q_1, q_2, q_4\}),$$ где $\delta$:\\
			\begin{tabular}{r||c}
			 & $1$\\
			 \hline\hline
			 $\to q_0$ & $\{q_1\}$\\
			 $\boxed{q_1}$ & $\{q_2\}$\\
			 $\boxed{q_2}$ & $\{q_3\}$\\
			 $q_3$ & $\{q_4\}$\\
			 $\boxed{q_4}$ & $\emptyset$\\
			\end{tabular}
			
		\item 
		Для детерминизации автомата достаточно \guillemotleftотбросить\guillemotright\ фигурные скобки в функции переходов $\delta$. Полученный автомат в графовом представлении имеет вид:

		\begin{tikzpicture}[>=stealth', /tikz/initial text=, node distance=2.5cm,auto,every state/.style={very thick}]
			\node[state,initial] (q_0) {$q_0$};
			\node[state,accepting] (q_1) [right of=q_0] {$q_1$};
			\node[state,accepting] (q_2) [right of=q_1] {$q_2$};
			\node[state] (q_3) [right of=q_2] {$q_3$};
			\node[state,accepting] (q_4) [right of=q_3] {$q_4$};	
			\path[->] 
				(q_0) edge node {1}(q_1)
				(q_1) edge node {1} (q_2)
				(q_2) edge node {1} (q_3)
				(q_3) edge node {1} (q_4);
		\end{tikzpicture}

		Так как автомат без петель, воспользуемся формулой~\eqref{lengsOfWords} и получим: $$M = \{1, 2, 4\}.$$
	\end{enumerate}
\end{Exmpl}

\begin{Exmpl}
    (Бесконечный регулярный язык)\\
    Вход: Праволинейная грамматика $G = (\{S, D, T\}, \{a, b\}, \mathcal P, S)$, $\mathcal P$:
    \begin{equation*}
        \begin{array}{l}
            S \to aa \mid bbb \mid aaD \mid bbbT \\
            D \to aa \mid aaD \\
            T \to bbb \mid bbbT
        \end{array}
    \end{equation*}
    \begin{enumerate}
        \item Построим грамматику отождествления $L(G):$
            \begin{equation*}
                \begin{array}{l}
                    S \to 11 \mid 111 \mid 11D \mid 111T \\
                    D \to 11 \mid 11D \\
                    T \to 111 \mid 111T
                \end{array}
            \end{equation*}
        \item Автомат, читающий $\Id(L(G))$, может выглядеть так:\\
			\begin{tikzpicture}[>=stealth', /tikz/initial text=, node distance=2cm,auto,every state/.style={very thick}]
				\node[state,initial] (q_0) {$q_0$};
				\node[state] (q_1) [right of=q_0] {$q_1$};
				\node[state,accepting] (q_2) [right of=q_1] {$q_2$};
				\node[state] (q_3) [right of=q_2] {$q_3$};
				\node[state] (q_4) [below of=q_0] {$q_4$};	
				\node[state] (q_5) [right of=q_4] {$q_5$};
				\node[state,accepting] (q_6) [right of=q_5] {$q_6$};
				\node[state] (q_7) [right of=q_6] {$q_7$};
				\node[state] (q_8) [right of=q_7] {$q_8$};
				\path[->] 
					(q_0) edge node {1}(q_1)
					(q_1) edge node {1} (q_2)
					(q_2) edge node {1} (q_3)
					(q_3) edge[bend left] node {1} (q_2)
					(q_0) edge node {1}(q_4)
					(q_4) edge node {1}(q_5)
					(q_5) edge node {1}(q_6)
					(q_6) edge node {1}(q_7)
					(q_7) edge node {1}(q_8)
					(q_8) edge[bend left]  node {1}(q_6);
			\end{tikzpicture}
        \item После детерминизации автомат примет вид:\\
            \begin{tikzpicture}[>=stealth', /tikz/initial text=, node distance=2cm,auto,every state/.style={very thick}]
                \node[state,initial] (q_0) {$\{q_0\}$};
                \node[state] (q_1) [right of=q_0] {$\scriptstyle \{q_1, q_4\}$};
                \node[state,accepting] (q_2) [right of=q_1] {$\scriptstyle \{q_2, q_5\}$};
                \node[state,accepting] (q_3) [right of=q_2] {$\scriptstyle \{q_3, q_6\}$};
                \node[state,accepting] (q_4) [right of=q_3] {$\scriptstyle \{q_2, q_7\}$};	
                \node[state] (q_5) [right of=q_4] {$\scriptstyle \{q_3, q_8\}$};
                \node[state,accepting] (q_6) [below of=q_5] {$\scriptstyle \{q_2, q_6\}$};
                \node[state] (q_7) [left of=q_6] {$\scriptstyle \{q_3, q_7\}$};
                \node[state,accepting] (q_8) [left of=q_7] {$\scriptstyle \{q_2, q_8\}$};
                \path[->] 
                    (q_0) edge node {1}(q_1)
                    (q_1) edge node {1}(q_2)
                    (q_2) edge node {1}(q_3)
                    (q_3) edge node {1}(q_4)
                    (q_4) edge node {1}(q_5)
                    (q_5) edge node {1}(q_6)
                    (q_6) edge node {1}(q_7)
                    (q_7) edge node {1}(q_8)
                    (q_8) edge node {1}(q_3);
            \end{tikzpicture}
     
		\item Автомат после детерминизации содержит цикл. Воспользуемся формулой \ref{lengsOfWordsCycle}: $$M = \{2, \AP(3, 6), \AP(4, 6), \AP(6, 6), \AP(8, 6)\}$$.
	\end{enumerate}
\end{Exmpl} 


\section{Множество длин слов контекстно-свободного языка}\label{LengthsCFChap}

В этой части приводится алгоритм, позволяющий найти множество длин слов контекстно\nbdash{}свободного языка. С этой целью будут развиты идеи, изложенные в части \ref{LengthsPLChap}.

Пусть $L$~--- контекстно\nbdash{}свободный язык, $M(L)$~--- это множество длин слов языка $L$, а $M(L)_{\leqslant k}$~--- подмножество $M(L)$, состоящее из элементов, меньших или равных $k$: $M(L)_{\leqslant k} = \{a \in M(L), a \leqslant k \}$. 

\begin{Lmm}
	Множество $M(L)_{\leqslant k}$ можно записать явно.
\end{Lmm}
\begin{proof}
	Построим по контекстно\nbdash{}свободной грамматике автомат читающий $\Id(L)$ (для этого можно использовать алгоритм \ref{CFG4Id}) и подадим ему на вход слова вида $1^i$, где $i = 0, \ldots, k$. Те значения $i$, при которых автомат распознал соответствующее слово, добавим в множество $M(L)_{\leqslant k}$. Эту процедуру можно проделать для любого конечного $k$.
\end{proof}

Пусть $N$~--- это константа, фигурирующая в лемме о накачке. Как следует из доказательства леммы, $N$ можно вычислить по контекстно\nbdash{}свободной грамматике $G$ и оно равно $2^m$, где $m$~--- это количество нетерминалов грамматики $G_H$, причём $L(G) = L(G_H)$ и $G_H$ находится в нормальной форме Хомского.

Рассмотрим два случая. Предположим, язык $L$ конечный. Тогда $M(L) = M(L)_{\leqslant N}$. Действительно, если бы языку принадлежало слово длиннее $N$, ему принадлежала бы и арифметическая последовательность, содержащая это слово, что противоречит конечности языка.

Будем считать, что язык бесконечный. По теореме \ref{PumpingLangsAreSimple} язык $\Id(L)$ праволинейный. Значит для $\Id(L)$ можно построить детерминированный конечный автомат. Для одного и того же языка $\Id(L)$ можно построить разные детерминированные автоматы. Пусть $\{A_i\}$~--- это все такие автоматы, $F_i$~--- множество допускающих состояний автомата $A_i$. С каждым автоматом свяжем число $D(A_i)$~--- расстояние от начального состояния до самого дальнего допускающего состояния: $D(A_i) = max_{f \in F_i} d(q_0, f)$. Среди всех детерминированных конечных автоматов, читающих $\Id(L)$, выберем автомат $A_k$ с наименьшим числом $D$ и обозначим его через $A$, $D = D(A) = min \{D(A_i)\}$. Автомат $A$ имеет вид \ref{AutomataForInfiniteLang}, поскольку мы в предположении, что язык $L$ бесконечный, а все автоматы, читающие $\Id(L)$ имели вид \ref{AutomataForFiniteLang} (для конечного языка) и \ref{AutomataForInfiniteLang} (для бесконечного). Глядя на автомат, легко заметить, что верны следующие утверждения.

\begin{enumerate}
    \item Любое слово не короче $D$ принадлежит хотя бы одной арифметической прогрессии, причём её первый член меньше или равен $D$, а шаг меньше или равен $n$ ($n$~--- число состояний автомата).
	%\item Если слово $w$ принадлежит некоторой арифметической прогрессии и его длина не меньше $D$, то существует слово $w' = abc$ из $\Id(L)$, такое что $|ac| \leqslant D, |b| \leqslant n$ и существует $k: w = ab^kc$.
    \item\label{EqualsSteps} Для описания множества длин слов можно выбрать набор арифметических прогрессий с равным шагом $\{\AP(a_i, d)\}, i \in \{1, \ldots, k\}$. Причём наименьшее возможное $d$ равно длине цикла автомата $A$.
\end{enumerate}

Мы не можем найти $D$, так как пока не умеем строить конечный автомат по контекстно\nbdash{}свободной грамматике $\Id(L)$. В то же время, для $\Id(L)$ выполняется лемма о накачке для контекстно\nbdash{}свободных языков с параметром $N$, который, повторим, можно вычислить. $N$ не может быть меньше $D$: $N \geqslant D$. Потому, если для $D$ выполняются утверждения выше, то для $N$ они выполняются тем более. Лемма о накачке уже давала ограничение на шаг прогрессий ($\leqslant N$), а сейчас получено ограничение на первый член прогрессии ($\leqslant D \leqslant N$). Получаем, что можно выбрать набор арифметических прогрессий, описывающих множество длин слов языка $L$ так, чтобы первые члены и шаги этих прогрессий были меньше $N$. Это очень важное свойство и оно пригодится в дальнейшем при построении алгоритма \ref{FindLenthsCFAlg} нахождения длин слов контекстно\nbdash{}свободного языка. Для лучшего понимания этого алгоритма надо иметь ввиду, что хоть мы и получили ограничение на первый член прогрессии и оно равно $N$, удобнее считать, что первые члены лежат в промежутке от $N$ до $2N$. Дело в том, что слова короче $N$ могут являться, а могут и не являться первыми членами прогрессий с ненулевым шагом. В то же время в диапазоне от $N$ до $2N$ все слова принадлежат какой-либо прогрессии и при нахождении длин можно считать, что они и есть первые члены прогрессий, те же, что короче $N$ можно добавить во множество длин слов <<вручную>>. 

Используя факт \ref{EqualsSteps}, можно ограничиться рассмотрением наборов арифметических прогрессий с фиксированным шагом. Приведём вспомогательный алгоритм, позволяющий такие наборы сравнивать на равенство. Пусть $P$~--- набор арифметических прогрессий, через $M(P)$ обозначим множество чисел, содержащихся хотя бы в одной из прогрессий. 

\begin{NumAlgo}[Проверка совпадения двух наборов арифметических прогрессий]\label{EqualsAP}
    \nspace\\
    \textsc{Вход}: $P_1, P_2$~--- два заданных набора арифметических прогрессий: \\ $P_1 = \{AP(a_1,d_1)$, $AP(a_2,d_1)$, $\ldots, AP(a_m,d_1)\},$ \\
	$P_2 = \{AP(b_1,d_2), AP(b_2,d_2), \ldots, AP(b_l,d_2)\}$. \\
    \textsc{Выход}: <<Да>>, если $M(P_1) = M(P_2)$, и <<Нет>> в противном случае.
    \begin{enumerate}
        \item $d \gets LCM(d_1, d_2)$
        \item $t_1 \gets d/d_1$
        \item $t_2 \gets d/d_2$
        \item\label{SetPi} ${P'}_1 \gets \{AP(a_1+i*d_1, d), AP(a_2+i*d_1, d), \ldots, AP(a_m+i*d_1, d) \mid i \in {0, \ldots, t_1 - 1} \}$\\		
			  $ {P'}_2 \gets \{AP(b_1+i*d_2,d), AP(b_2+i*d_2,d), \ldots, AP(b_l+i*d_2,d) \mid i \in {0, \ldots, t_2-1} \}$
        \Comment Строим из $P_1$ набор прогрессий ${P'}_1$ с шагом $d$ такой что $M(P_1) = M({P'}_1)$. Аналогично для $P_2$.
        \item $S_1 \gets \{a_j + i*d_1 \mid j=1, \ldots, m, \; i = 0, \ldots, t_1-1 \}$\\
			  $S_2 \gets \{b_j + i*d_2 \mid j=1, \ldots, l, \; i = 0, \ldots, t_2-1 \}$
		\item ${S'}_1 \gets S_1.$ Для каждой пары элементов $a, b$ из $S_1$ таких что $a<b$ и $a \equiv b\pmod{d}$ исключим $b$ из ${S'}_1$: ${S'}_1 \gets {S'}_1 \setminus \{b\}$.
		\item ${S'}_2 \gets S_2.$ Для каждой пары элементов $a, b$ из $S_2$ таких что $a<b$ и $a \equiv b\pmod{d}$ исключим $b$ из ${S'}_2$: ${S'}_2 \gets {S'}_2 \setminus \{b\}$.
        \item Множества ${S'}_1, {S'}_2$ конечны. Их можно проверить на равенство за конечное время. Если ${S'}_1 = {S'}_2$, то вернуть <<Да>>, в противном случае <<Нет>>.
    \end{enumerate}
\end{NumAlgo}

\begin{Lmm}
	Пусть ${S'}_1, {S'}_2 \subset \N_0$ и существует $d$ (общее для ${S'}_1, {S'}_2$), такое что любые $a, b \in {S'}_1 ({S'}_2)$ не равны по модулю $d$: $a \not\equiv b \pmod{d}$. Через $P_i, i \in {1,2}$ обозначим набор арифметических прогрессий с шагом $d$ и первым членом из ${S'}_i$: $P_i = \{\AP(a,d) \mid a \in {S'}_i \}$. Тогда $M(P_1) = M(P_2)$ тогда и только тогда, когда ${S'}_1 = {S'}_2.$  
\end{Lmm}
\begin{proof}
	Ясно, что если ${S'}_1 = {S'}_2,$ то $M(P_1) = M(P_2).$ 
	
	Предположим обратное неверно: $M(P_1) = M(P_2)$ и ${S'}_1 \neq {S'}_2$. $\exists a \in {S'}_1, a \not\in {S'}_2$ $\implies a \in M(P_1)$  $\implies a \in M(P_2)$ (так как $M(P_1) = M(P_2)$ по условию) $\implies \exists b \in {S'}_2, \; i \in \N \mid b + id = a \in M(P_2)$ $\implies b \in M(P_2) = M(P_1)$ $\implies \exists c \in {S'}_1, \; j \in \NO \mid c+jd = b.$ Получаем, $\exists c \in {S'}_1, i \in \N, \; j \in \NO \mid c+(i+j)d = c+jd + id = b + id = a.$ Но это значит, что $a, c \in {S'}_1$ и равны по модулю $d$. Противоречие.
\end{proof}

\begin{Thm}[корректность алгоритма~\ref{EqualsAP}]
	Пусть $P_1, P_2$~--- два набора арифметических прогрессий. Алгоритм~\ref{EqualsAP} вернёт <<Да>> тогда и только тогда, когда $M(P_1) = M(P_2)$.	
\end{Thm}
\begin{proof}
	Предположим, $d_1 = d_2$, тогда $d = d_1 = d_2,$ $t_1 = t_2 = 1,$ ${P'}_1 = P_1,$ ${P'}_2 = P_2,$ $S_1 = \{a_1, a_2, \ldots, a_m\},$ $S_2 = \{b_1, b_2, \ldots, b_l\}$. Очевидно, что 
	$$
		M(\bigcup\limits_{a \in {S'}_1} {\AP(a,d)}) = M(\bigcup\limits_{a \in {S}_1} {\AP(a,d)}) \stackrel{def}{=} M(P_1).
	$$
	Для $M(P_2)$ аналогично. А по лемме $M(P_1) = M(P_2) \Leftrightarrow {S'}_1 = {S'}_2$. 
	
	Предположим, $d_1 \neq d_2$. Сведём этот случай к предыдущему. Для этого построим множества арифметических прогрессий $P_1', P_2'$, удовлетворяющие условиям:
	\begin{enumerate}
		\item $M(P_1) = M(P'_1)$;
		\item $M(P_2) = M(P'_2)$;
		\item\label{PiEqualsSteps} шаги прогрессий в $P_1'$ и $P_2'$ равны $d$.	
	\end{enumerate}
	Покажем, что наборы, предложенные на шаге \ref{SetPi} алгоритма удовлетворяют условиям выше. Условие \ref{PiEqualsSteps} выполняется автоматически, докажем первые два. Возьмём $b \in M(P_1)$, тогда существуют $a \in M(P_1)$ и $i \in \N_0$ для которых $a+id_1 = b$ и $a$~--- первый член прогрессии (иначе говоря, $a-d_1 \not\in M(P_1)$). Число $i$ представимо в виде $i = mt_1 + k$ для некоторых $m, k \in \N_0,$ $k < t_1.$ Получаем: 
	$$
		b = a+id_1 = a + (mt_1 + k)d_1 = a + m t_1 d_1 + k d_1 = a + k d_1 + m d = (a + k d_1) + m d.
	$$
	Число $(a + k d_1) + m d$ принадлежит $M(P_1')$ по построению. Докажем обратное вложение $M(P_1) \supset M(P'_1)$. Выберем некоторое $b \in M(P_1')$, по построению $b$ представляется в виде 
	$$
		b = a+id_1+jd = a + id_1+j t_1 d_1 = a + (i+j t_1) d_1.  
	$$
	Здесь $a+id_1$ --- первый член прогрессии из $P'_1$, несложно убедиться, что $a \in M(P_1)$ и, стало быть, $b \in M(P_1)$.
\end{proof}

\begin{NumAlgo}[Нахождение длин слов языка, заданного контекстно\nbdash{}свободной грамматикой]\label{FindLenthsCFAlg}
\nspace\\
\textsc{Вход}: Контекстно\nbdash{}свободная грамматика $G$.\\
\textsc{Выход}: Множество длин слов $M$ языка $L = L(G)$.
\begin{enumerate}
	\item Используя алгоритм \ref{CFG4Id}, получим грамматику $G'$ языка $\Id(L)$.
	\item Приведём $G'$ в нормальную форму Хомского. Получившуюся грамматику назовём $G_H$.
	\item $N \gets 2^{|F|}$, где $F$~--- множество нетерминалов $G_H$.
    \item Зная $G_H$, можно вывести все слова не длиннее $N$: $ M \gets M(L)_{\leqslant N}.$
	\item $T \gets M(L)_{\leqslant 2N} \setminus M(L)_{\leqslant N}$.
	\item Если $T$ пусто, то язык конечный. Вывести $M$ и завершить работу алгоритма. В противном случае, если $T$ не пусто, язык бесконечный. Перейти к следующему шагу.
    \item $I \gets \{1, \ldots, N\}$
	\item Для каждого натурального $d \in I$ построим множество арифметических прогрессий: $P_d \gets \{\AP(N, d), \AP(N+1, d), \ldots, \AP(N+d-1, d)\}$
    \Comment $P_d$~--- это набор прогрессий с шагом $d$ каждая.
    \item $P_d \gets P_d \cap \{AP(x, d) \mid  x \in M(L))_{\leqslant 2N}\}$
    \Comment В каждом из $P_d$ оставляем только те прогрессии, которые начинаются с элемента, принадлежащего $\Id(L)$.
    \item\label{AtLeastOne} $M_d \gets M(P_{d}) \cup M, d \in I.$
    \Comment Хотя бы для одного $d \in I$ верно, что $M_d = \Id(L)$.
    \item\label{OnlyOne} Для каждых $d_1, d_2 \in I,$ $d_1 < d_2$ проверить равны ли $M(P_{d_1})$ и $M(P_{d_2})$, используя алгоритм \ref{EqualsAP}. Если равны, то $I \gets I \setminus \{d_2\}.$
	\Comment Среди $P_d, d \in I$ остались наборы прогрессий, которые порождают различные множества. При этом теперь ровно одно из множеств $M_d$ совпадает с $\Id(L)$.
    \item\label{RunProgramsStep} Перебираем все целые $n$ от 0 до бесконечности. Для каждого из них проверяем условие: $n \in M_d \Leftrightarrow n \in M(L)$, где $d \in I$. Если для некоторого $d$ оно ложно, то $I \gets I \setminus \{d\}$. Перейти к следующему шагу, когда в $I$ останется один элемент: $|I| = 1$.
    \item Вывести $M_{d'}$.
	\Comment Зная множество $P_{d'}$ и конечное множество $M(L)_{\leqslant N}$ не составляет труда написать праволинейную грамматику. Напомним, что $M_{d'} = P_{d'} \cup M(L)_{\leqslant N}$.
\end{enumerate}
\end{NumAlgo}

\begin{Thm}[корректность алгоритма~\ref{FindLenthsCFAlg}]
	Дана контекстно\nbdash{}свободная грамматика $G$. Алгоритм~\ref{FindLenthsCFAlg} вернёт множество длин слов $M$ языка $L = L(G)$.
\end{Thm}
\begin{proof}
	Наша задача~--- найти всё множество $M(L)$ в виде конечного набора арифметических прогрессий. Вернёмся к автомату $A$, читающему контекстно\nbdash{}свободный язык $L$. Если бы стала известна длина его цикла $d$ (возможный шаг), можно было бы сразу выписать множество длин слов языка $L$: 
	$$
		M(L) = M(L)_{\leqslant N} \cup M(\{\AP(a, d) \mid a \in M(L), N \le a \le 2N]\}.
	$$
	Идея алгоритма \ref{FindLenthsCFAlg} проста. Нам известно, что шаг прогрессии не больше $N$ и что фиксируя шаг прогрессии, фиксируется сама прогрессия. Построим $N$ гипотез. Первая гипотеза: $d=1$, вторая: $d=2$, \ldots, $N$-ая: $d=N$. Среди гипотез есть хотя бы одна верная (шаг \ref{AtLeastOne}). Попарно сравним наборы прогрессий, получающиеся при разных $d$ и оставим только уникальные (шаг \ref{OnlyOne}). Среди оставшихся найдётся ровно одно $d \in I$ для которого $M_d = M(L)$. На шаге \ref{RunProgramsStep} одна за другой исключаются неверные гипотезы. Покажем, что при некотором конечном $n$ в наборе $I$ останется ровно один элемент, или, иными словами, шаг \ref{RunProgramsStep} завершится. Предположим, это не так. Тогда существуют $d_1, d_2 \in I$, $d_1 < d_2$, такие что для любого $n \in \NO$ верно: $n \in M_{d_1, d_2} \Leftrightarrow n \in M(L)$, то это означало бы, что $M(L) = M_{d_1}$ и $M(L) = M_{d_2}$, но множества $M_{d_1}$ и $M_{d_2}$ различны, поскольку если бы они были равны, то  на шаге \ref{OnlyOne} элемент $d_2$ был бы исключён из $I$. Пришли к противоречию.
\end{proof}

%\begin{Exmpl}[Нахождение множества длин слов контекстно\nbdash{}свободного языка.]
%	Рассмотрим контекстно\nbdash{}свободный язык $L$, порождающийся грамматикой $G = ({S, A, B}, {a, b}, \mathcal P, S)$, где $\mathcal P:$
%	\begin{array}{l}
%		S \to А \mid B
%		A \to aa \mid aaA
%		B \to bbb \mid bbbB
%	\end{array} 
	
%	\begin{enumerate}
%		\item 
%			Грамматика отождествлённого языка имеет вид $G' = ({S, A, B}, {1}, \mathcal P, S)$, где $\mathcal P:$
%			\begin{array}{l}
%				S \to А \mid B
%				A \to 11 \mid 11A
%				B \to 111 \mid 111B
%			\end{array}	
%		\item 
%			Грамматика $G'$ в нормальной форме Хомского может выглядеть так: $G_H = ({S, D_E, T_E, A, B, E}, {1}, \mathcal P, S)$, где $\mathcal P$ есть
%			\begin{array}{l}
%				S \to EE \mid E D_E \mid EEA \mid T_E B \\
%				D_E \to EE \\
%				T_E \to E D_E \\
%				A \to D_E A \\
%				B \to T_E B \\
%				E \to 1 \\
%			\end{array}
%		\item $N \gets 2^{|M|} = 2^{6} = 64.$
%		\item $M \gets M(L)_{\leqslant N} = {2, 3, 4, 6, 8, 9, \ldots, 64}.$
%		\item $T \gets M(L)_{\leqslant 2N} - M(L)_{\leqslant N} = \{66, 68, 69, 70, \ldots, 128 \}$.
%		\item $T$ не пусто. Значит, множество слов языка $\Id(L)$ бесконечное.
%		\item $I \gets \{1, \ldots , 64 \}.$
%		\item 
%		$P_1 \gets \{\AP(64, 1)\},$\\
%		$P_2 \gets \{\AP(64, 2), \AP(65, 2)\},$\\
%		\ldots \\
%		$P_64 \gets \{\AP(64, 64), \AP(65, 64), \AP(66, 64), \ldots, \AP(127, 64)\}.$
%		\item 
%		$P_1 \gets \{\AP(64, 1)\} \cap \{AP(x, 1) \mid  x \in M(L))_{\leqslant 128}\} = \{\AP(64, 1)\},$\\
%		$P_2 \gets \{\AP(64, 2), \AP(65, 2)\} \cap \{AP(x, 2) \mid  x \in M(L))_{\leqslant 128}\} = \{\AP(64, 2)\},$\\
%		\ldots \\
%		$P_64 \gets \{\AP(64, 64), \AP(65, 64), \AP(66, 64), \ldots , \AP(127, 64)\} \cap \{AP(x, 2) \mid  x \in M(L))_{\leqslant 128}\} = \{\AP(64, 64), \AP(66, 64), \AP(68, 64), \ldots , \AP(126, 64)\}.$
%		\item  $M_d \gets M(P_{d}) \cup M, d \in I.$		
%	\end{enumerate}
%\end{Exmpl}

\begin{Exmpl}[Нахождение множества длин слов языка $ww^R$]
	Рассмотрим контекстно\nbdash{}свободный язык $L$, порождающийся грамматикой $G = (\{S\}, \{a, b\}, \mathcal P, S)$, где $\mathcal P$:
	\begin{equation*}
	\begin{array}{l}
		S \to ab \mid aSa \mid bSb
	\end{array}	
	\end{equation*}
	
	\begin{enumerate}
		\item 
			Грамматика отождествлённого языка имеет вид $G' = (\{S\}, \{1\}, \mathcal P, S)$, где $\mathcal P:$
			\begin{equation*}
			\begin{array}{l}
				S \to 11 \mid 1S1
			\end{array}	
			\end{equation*}
		\item 
			Грамматика $G'$ в нормальной форме Хомского может выглядеть так: $G_H = ({S, T, E}, {1}, \mathcal P, S)$, где $\mathcal P$ есть
			\begin{equation*}
			\begin{array}{l}
				S \to EE \mid T E \\
				T \to ES \\
				E \to 1
			\end{array}
			\end{equation*}
		\item $N \gets 2^{|F|} = 2^{3} = 8.$
		\item $M \gets {2, 4, 6, 8}.$
		\item $T \gets M(L)_{\leqslant 2N} \setminus M(L)_{\leqslant N} = \{2,4,6,8,10,12,14,16\} \setminus \{2, 4, 6, 8\} = \{10,12,14,16\}$.
		\item Множество $T$ не пусто. Значит, множество слов языка $\Id(L)$ бесконечное.
		\item $I \gets \{1, \ldots , 8 \}.$
		\item $P_1 \gets \{\AP(8, 1)\},$\\
		$P_2 \gets \{\AP(8, 2), \AP(9, 2)\},$\\
		$P_3 \gets \{\AP(8, 3), \AP(9, 3), \AP(10, 3)\},$\\
		\ldots \\
		$P_8 \gets \{\AP(8, 8), \AP(9, 8), \AP(10, 8), \ldots , \AP(15, 8)\}.$
		\item $M(L)_{\leqslant 2N} = \{2,4,6,8,10,12,14,16\}$. Для каждого $d \in I$ положим
		$$
			P_d \gets P_d \cap \{AP(x, d) \mid  x \in M(L))_{\leqslant 2N}\}.
		$$
		$P_1 \gets \{\AP(8, 1)\},$\\
		$P_2 \gets \{\AP(8, 2)\},$\\
		$P_3 \gets \{\AP(8, 3), \AP(10, 3)\},$\\
		\ldots \\
		$P_8 \gets \{\AP(8, 8), \AP(10, 8), \ldots , \AP(14, 8)\}.$
		\item  $M_d \gets M(P_{d}) \cup M,$ $d \in I.$		
		\item $I \gets \{1, 2, 3, 5, 7 \}$.
		\item Начнём перебирать целые $n$ от 0 до бесконечности.\\
        При $n$ от 0 до 8 никаких изменений с $I$ не происходит.\\
        $n = 9:$ $n \in M_1$, но $n \not\in M(L)$ и  $I \gets \{2, 3, 5, 7 \}$.\\
        $n = 10:$ $n \in M_d \Leftrightarrow n \in M(L)$, для любого $d \in I$.\\
        $n = 11:$ $n \in M_3$, но $n \not\in M(L)$ и  $I \gets \{2, 5, 7 \}$.\\
        $n = 12:$ $n \in M_d \Leftrightarrow n \in M(L)$, для любого $d \in I$.\\
        $n = 13:$ $n \in M_5$, но $n \not\in M(L)$ и  $I \gets \{2, 7\}$.\\
        $n = 14:$ $n \in M_d \Leftrightarrow n \in M(L)$, для любого $d \in I$.\\
        $n = 15:$ $n \in M_7$, но $n \not\in M(L)$ и  $I \gets \{2\}$.
		\item Вывести $M_2$.
	\end{enumerate}
\end{Exmpl}

%\begin{Exmpl}[Ограниченный язык Дика]	
	%Рассмотрим контекстно\nbdash{}свободный язык Дика, порождающийся грамматикой $G = ({S, A, B, U}, {(, ), [, ]}, \mathcal P, S)$, где $\mathcal P:$
	%\begin{array}{l}
	%	S \to \epsilon \mid AS \mid BS \\
	%	A \to () \mid (U) \\
	%	B \to [] \mid [U] \\
	%	U \to A \mid B \mid AU \mid BU
	%\end{array}	
	%
	%\begin{enumerate}
	%	\item Грамматика в нормальной форме Хомского может выглядеть так: $G_H = (M, {(, ), [, ]}, \mathcal P, S)$, где $\mathcal P$ есть
	%	\begin{array}{l}
	%		S \to \epsilon \mid AS \mid BS \\
	%		A \to A_( A_) \mid U_( A_) \\
	%		U_( \to A_( U \mid A_( A \mid A_( B\\
	%		A_( \to ( \\
	%		A_) \to ) \\
	%		B \to B_[ B_] \mid U_[ B_] \\
	%		U_[ \to B_[ U \mid B_[ A \mid B_[ B \\
	%		B_[ \to [ \\
	%		B_] \to ] \\
	%		U \to AU \mid BU \mid AA \mid AB \mid BA \mid BB
	%	\end{array}	
	%	Отсюда $N = 2^{|M|} = 2^{10}.$
	%\end{enumerate}	
%\end{Exmpl}


\section{Множество длин слов контекстно-зависимого языка}\label{LengthsCSChap}

Покажем, что проблема нахождения длин слов контекстно\nbdash{}зависимого языка неразрешима. Для этого воспользуемся неразрешимостью проблемы пустоты контекстно\nbdash{}зависимого языка \cite[стр. 160]{Das}.

\begin{Thm}
	Проблема нахождения множества длин слов контекстно\nbdash{}зависимого языка неразрешима.
\end{Thm}
\begin{proof}
	Поведём доказательство от противного. Предположим, проблема нахождения длин слов разрешима, но тогда разрешима проблема пустоты контекстно\nbdash{}зависимого языка. Противоречие.
\end{proof}


\section{Связанные задачи}\label{ApplicationChap} 

Рассмотрим язык $L$ над произвольным алфавитом $\Sigma$. Через $L^{(a)}, a \in \Sigma$ обозначим множество слов языка $L$, состоящих только из букв $a$: 
$$
	L^{(a)} = \{w \in L \mid \exists n \in \NO \; w = a^n \}.
$$
Через $L|_{a}, a \in \Sigma$ обозначим множество слов, полученных из слов языка $L$ вычёркиванием букв отличных от $a$.

\begin{Exmpl}
	Пусть язык $L$ конечен и $L = \{ aa, abb, abc, aad, aaaa \}.$ Тогда $L^{(a)} = \{aa, aaaa\}$ и $L|_{a} = \{a, aa, aaaa\}$.
\end{Exmpl}

Используя материалы данной статьи, легко найти множество длин этих языков и их класс в иерархии Хомского.

Пусть язык $L$ порождается грамматикой $G = (N, \Sigma, \mathcal P, S \in N)$. Тогда язык $L^{(a)}$ можно породить грамматикой $G' = (N \cup (\Sigma \setminus \{a\}), \{a\}, \mathcal P, S \in N)$. В $G'$ множество продукций осталось таким же как в $G$. Все терминалы (кроме $a$) стали нетерминалами, что обеспечило невыводимость слов, содержащих буквы помимо $a$. Грамматика $L|_{a}$ строится чуть сложнее.

\begin{NumAlgo}[Построение грамматики языка $L|_{a}$.]
\nspace\\
\textsc{Вход}: Грамматика $G = (N, \Sigma, \mathcal P, S \in N)$ языка $L$.\\
\textsc{Выход}: Грамматика $G' = (N, \{a\}, \mathcal P', S \in N)$, такая что $L(G') = L|_{a}$.
\begin{enumerate}
    \item В каждой продукции $p \in \mathcal P$ все буквы из $\Sigma \setminus \{a\}$ заменить на пустое слово. 
	\item Полученные на предыдущем шаге продукции добавить во множество продукций $\mathcal P'$.
\end{enumerate}
\end{NumAlgo}

\begin{Remark}
	Алгоритмы построения грамматик для $L^{(a)}$ и $L|_{a}$ работают для праволинейной, контекстно\nbdash{}свободной и контекстно\nbdash{}зависимой грамматики $G$.
\end{Remark}

Теоремы о корректности алгоритмов построения грамматик для $L^{(a)}$ и $L|_{a}$ оставим читателю. 

Языки $L^{(a)}$ и $L|_{a}$ --- это языки над однобуквенным алфавитом. Из построений видно, что если язык $L$ контекстно\nbdash{}свободен, то $L^{(a)}$ и $L|_{a}$ также контекстно\nbdash{}свободны, следовательно, можно найти множество длин слов $L^{(a)}$ и $L|_{a}$ используя алгоритм \ref{FindLenthsCFAlg}. Более того, из следствия \ref{IdCFIsNoCF} вытекает, что языки $L^{(a)}$ и $L|_{a}$ праволинейны. Если $L$ контекстно\nbdash{}зависимый, то языки $L^{(a)}$ и $L|_{a}$, в общем случае, контекстно\nbdash{}зависимы. Проблема нахождения длин слов для каждого из них неразрешима.


%\begin{Thm}
%	Верны следующие утверждения.
%	\begin{enumerate}
%		\item Язык $L^{(a)}$ является языком над однобуквенным алфавитом $\{a\}$. 
%		\item Сложность $L^{(a)}$, с точки зрения иерархии Хомского, не превосходит сложность языка $L$.
%		\item Если $L$ контекстно\nbdash{}свободен, то $L^{(a)}$ праволинеен.
%	\end{enumerate}
%\end{Thm}
%\begin{proof}
%	\begin{enumerate}
%		\item Верно по построению $L^{(a)}$. 
%		\item Продукции в грамматике $L^{(a)}$ совпадают с продукциями для языка $L$.
%		\item Если $L$ контекстно\nbdash{}свободен, то грамматика для $L^{(a)}$ останется контекстно\nbdash{}свободной, поскольку содержит все те же продукции. По следствию \ref{IdCFIsNoCF} из теоремы \ref{PumpingLangsAreSimple} язык $L^{(a)}$ праволинеен.
%	\end{enumerate}
%\end{proof}

%\begin{Thm}
%	Верны следующие утверждения.
%	\begin{enumerate}
%		\item Язык $L|_{a}$ является языком над однобуквенным алфавитом $\{a\}$. 
%		\item Его сложность, с точки зрения иерархии Хомского, не превосходит сложность языка $L$.
%		\item Если $L$ контекстно\nbdash{}свободен, то $L|_{a}$ праволинеен.
%	\end{enumerate}
%\end{Thm}
%\begin{proof}
%	\begin{enumerate}
%		\item Верно по построению $L|_{a}$. 
%		\item Каждая продукция из $G'$ или такая же как в $G$ или стала проще. Чисто формально проблема возникает когда $G$ праволинейна. В этом случае в $G'$ могли появиться цепные продукции (то есть правила вида $A \to B, \; A, B \in N$), которые формально запрещены в праволинейных грамматиках. Построение алгоритма удаления цепных продукций оставим это читателю.
%		\item Если $L$ контекстно\nbdash{}свободен, то грамматика для $L|_{a}$ останется контекстно\nbdash{}свободной. По следствию \ref{IdCFIsNoCF} из теоремы \ref{PumpingLangsAreSimple} язык $L|_{a}$ праволинеен.
%	\end{enumerate}
%\end{proof}


\begin{thebibliography}{1}
    \bibitem{Lando} Ландо~C. К. Лекции о производящих функциях.~---3-е изд., испр.~--- М.: МЦНМО, 2007.~--- 144 с.
	\bibitem{Pen} Пентус А. E., Пентус М. Р. Теория формальных языков: Учебное пособие.~--- М.: Изд-во ЦПИ при механико-математическом ф-те МГУ, 2004.~--- 80 с.
	\bibitem{HMU} Хопкрофт Дж., Мотвани Р., Ульман Дж. Введение в теорию автоматов, языков и вычислений.~--- 2\nbdash{}е изд.~--- М.: Вильямс, 2002.~--- 528 с.	
    \bibitem{Erus} Ерусалимский Я. М. Дискретная математика: теория, задачи, приложения.~--- 3\nbdash{}е изд.~--- М.: Вузовская книга, 2000.~--- 280 с.	
	\bibitem{Das} Calude Cristian S., Calude Elena, Dinneen M. J. DLT 2004, Volume 8. Lecture Notes in Computer Science~--- Springer, 2004.~--- 429 с.
	
	% http://books.google.ru/books?id=z_-SzxRaZ4sC&pg=PA161&lpg=PA161&dq=The+emptiness+problem+context-sensitive+grammars+undecidable.&source=bl&ots=BkpQyQX4q8&sig=yGl1nf40nctOgyZc1a_bDkZ6jnU&hl=en&sa=X&ei=rTxrUaj6Aqbx4QSM4IDwCw&ved=0CC0Q6AEwADgU#v=onepage&q=The%20emptiness%20problem%20context-sensitive%20grammars%20undecidable.&f=false
\end{thebibliography}

\end{document}